This application claims benefit of priority under 35 U.S.C. xc2xa7119 to Japanese Patent Application No. H11-57596, filed on Mar. 4, 1999, the entire contents of which are incorporated by reference herein.
1. Field of the Invention
The present invention relates generally to a switching element and a packet switch. More specifically, the invention relates to a switching element for use in a packet switch on an input buffer system, and a packet switch on an input buffer system.
2. Description of Related Background Art
As a device for switching a fixed-length packet, there is an asynchronous transfer mode (ATM) switch. FIG. 11 shows the construction of a conventional ATM switch. As shown in FIG. 11, the ATM switch has a plurality of ATM cell transmitting mechanisms.
That is, as shown on the left in FIG. 11, the ATM switch has nine input ports IP0 through IP8, which are connected to nine input links Link 10 through Link 18, respectively. In addition, as shown on the right in FIG. 11, the ATM switch has nine output ports OP0 through OP8, which are connected nine output links Link 20 through Link 28, respectively. The ATM switch also has a switching network for transferring a cell, which is inputted from an optional input link of the input links Link 10 through Link 18, to an optional output link of the output links Link 20 through Link 28.
The switching network of the ATM switch comprises a plurality of switching elements SE00_00 through SE10_10, which are arranged in the form of lattice to be connected to each other. In the example of FIG. 11, there is shown a multistage connection construction of three stages assuming that a column of three switching elements arranged in vertical directions is one stage. One switching element in a certain stage is capable of transmitting a cell to all of the switching elements in the next stage.
The cell has destination information in its header, so that the cell transmitted from one of the input ports IP0 through IP8 to the switching network is designed to autonomously arrive at a target output port of the output ports OP0 through OP8 via each of the switching elements SE00_00 through SE10_10. Each of the switching elements SE00_00 through SE10_10 analyzes the destination information of the header of the cell, and transmits the cell to a target switching element in the next stage. Finally, the switching elements SE00_00 through SE10_10 in the third stage transmit the cell to a target one of the output ports OP0 through OP8.
One of the characteristics of the ATM switch is that when a cell transmitted from each of the input ports IP0 through IP8 in a certain cell cycle collides with another cell to be discarded, the ATM switch has the function of selecting a cell transmitting path different from the initial path in the next cell cycle to inhibit the cells from colliding with each other in the switching network.
The switching procedure will be described in detail below. The switching elements SE00_00 through SE10_00 in the first stage are designed to transmit cells, which are inputted from the input ports IP0 through IP8, to an optional switching element randomly selected from the switching elements SE00_01 through SE10_01 in the second stage.
At this time, if a cell collides with another cell in any one of the switching elements SE00_01 through SE10_01 in the second stage to be discarded without being selected by an arbiter, which is provided in each of the switching elements, so as not to arrive at a target one of the output ports OP0 through OP8, a negative acknowledge signal is returned to a corresponding one of the input ports IP0 through IP8, from which the discarded cell has been transmitted.
If a cell arrives at a target one of the output ports OP0 through OP8 without colliding with another cell in any one of the switching element SE00_01 through SE10_01 in the second stage, the negative acknowledge signal is not returned to the corresponding one of the input ports IP0 through IP8, from which the cell has been transmitted. In addition, even if a cell collides with another cell in any one of the switching element SE00_01 through SE10_01 in the second stage, if the cell is selected by the arbiter, which is provided in each of the switching elements, to arrive at a target one of the output ports OP0 through OP8, the negative acknowledge signal is not returned to corresponding one of the input port IP0 through IP8, from which the cell has been transmitted.
The negative acknowledge signal is generated in each of the switching elements SE00_01 through SE10_01. If a plurality of cells passing through the same output path are inputted to any one of the switching elements SE00_01 through SE10_01, the switching element performs conciliation in accordance with a predetermined algorithm to select and output any one of the cells. Then, the above described negative acknowledge signal is returned to a corresponding one of the input ports IP0 through IP8, from which an unselected one of the cells has been transmitted. The corresponding one of the input ports IP0 through IP8 having received the negative acknowledge signal retransmits the discarded cell in the next cell cycle since the cell transmitted therefrom has been discarded. At this time, a cell transmitting path (routing pattern) different from the cell cycle is selected.
In order to change the cell transmitting path (routing pattern), each of the switching elements SE00_00 through SE10_00 in the first stage has the function of transmitting a cell to any one of the switching elements SE00_01 through SE10_01 in the second stage. Then, a corresponding one of the switching elements SE00_00 through SE10_00 in the first stage transmits a cell to any one of the switching elements SE00_01 through SE10_01 in the second stage, which is different from that in the cell cycle, to change the cell transmitting path.
When the transmission of a cell ends in failure in the first cell cycle to retransmit the cell in the second cell cycle, it is possible to select a cell transmitting path, by which the number of discarded cells is smaller, in accordance with a predetermined algorithm. For example, the Evil-Twin algorithm is known as such an algorithm. By transmitting the cell in the second cell cycle in accordance with this algorithm, the number of collisions of cells in the switching network can be smaller than that when the cell is randomly transmitted in the second cell cycle.
As can be seen from the foregoing, in the conventional ATM switch, each of the input ports IP0 through IP8 selects only one cell transmitting path in one cell cycle. Then, when the first transmission of a cell ends in failure, the second transmission of the cell is tried in the next cell cycle. Therefore, there is a problem in that the probability of succeeding in the transmission of the cell by the first try is low. That is, there is a problem in that cells are easy to collide with each other in the switching network so that the network is clogged with the cells to reduce throughput. Such a problem tends to increase as the scale of the network increases.
FIG. 12 shows a status wherein, in a certain cell cycle, a cell to be transmitted from an input link Link 10 toward an output link Link 22 is inputted, and a cell to be transmitted from an input link Link 14 toward an output link Link 20 is inputted. By a routing pattern A shown in FIG. 12, these two cells collide with each other in a switching element SE00_01 in the second stage. Therefore, for example, the cell transmitted from the input link Link 14 is discarded without being selected by an arbiter, which is provided in the switching element SE00_01. The routing pattern A is herein a pattern determined at random or in accordance with a predetermined algorithm.
On the other hand, even in the same status as that in FIG. 12, it is possible to avoid the cell collision by a routing pattern B shown in FIG. 13. That is, by changing the path for one of the cells, it is possible to avoid the collision of the cells in the switching element SE00_01 in the second stage to transmit the cells to the target output links Link 22 without discarding the two cells. The routing pattern B is herein a pattern complementary to the routing pattern A.
Thus, in the conventional ATM switch, it is not possible to previously estimate a routing pattern, by which the number of cells to be discarded is small, before cells are transmitted from the input ports IP0 through IP8 to the switching network, so that there it problem in that the throughput in the ATM switch decreases.
It is therefore an object of the present invention to eliminate the aforementioned problems and to increase the number of passing cells by one cell transmitting try to decrease a cell residence time in an input port to improve the effective throughput in the whole switch.
In order to accomplish the aforementioned and other objects, according to one aspect of the present invention, a switching element for use in a packet switch, comprises; a crossbar switch for inputting packets from a plurality of packet input paths and for outputting the packets from one of a plurality of packet output paths in accordance with routing pattern information included in the packets; and an arbiter for inputting request packets from a plurality of request input paths and for outputting the request packets from one of a plurality of request output paths in accordance with routing pattern information included in the request packets, the arbiter selecting and outputting one of the request packets when the request packets are to collide with each other to be outputted to the same request output path of the plurality of request output paths.
According to another aspect of the present invention, a packet switch comprises: a plurality of input ports for accumulating and sequentially transmitting inputted packets and for transmitting first request packets by a first routing pattern and second request packets by a second routing pattern; a switching network for sequentially outputting the packets and the first and second request packets, which have been inputted from the plurality of input ports, to a target output port via a plurality of switching elements arranged in the form of lattice, each of the switching elements including: a crossbar switch for inputting the packets from a plurality of packet input paths and for outputting the packets from one of a plurality of packet output paths in accordance with routing pattern information included in the packets; a first arbiter for inputting the first request packets from a plurality of first input paths and for outputting the first request packets from one of a plurality of first output paths in accordance with routing pattern information included in the first request packets, the first arbiter selecting and outputting one of the first request packets when the first request packets are to collide with each other to be outputted to the same first output path of the plurality of first output paths; and a second arbiter for inputting the second request packets from a plurality of second input paths and for outputting the second request packets from one of a plurality of second output paths in accordance with routing pattern information included in the second request packets, the second arbiter selecting and outputting one of the second request packets when the second request packets are to collide with each other to be outputted to the same second output path of the plurality of second output paths; and a result output circuit for outputting a comparison result indicative signal for causing the input port to transmit packets by one of the first and second routing patterns in next cycle, by which more request packets have reached the output port, on the basis of the result of transmission of the first and second request packets.
According to another aspect of the present invention, a packet switch comprises: a plurality of input ports for accumulating and sequentially transmitting inputted packets, and for transmitting first request packets by a first routing pattern in the first half of a cycle before the packets are transmitted and for transmitting second request packets by a second routing pattern in the second half of the cycle; a switching network for sequentially outputting the packets and the first and second request packets, which have been inputted from the plurality of input ports, to a target output port via a plurality of switching elements arranged in the form of lattice, each of the switching elements including: a crossbar switch for inputting the packets from a plurality of packet input paths and for outputting the packets from one of a plurality of packet output paths in accordance with routing pattern information included in each of the packets; and an arbiter for inputting the first and second request packets from a plurality of request input paths and for outputting the first and second request packets from one of a plurality of request output paths in accordance with routing pattern information included in the first and second request packets, the arbiter selecting and outputting one of the first request packets when one of the first request packets collide with another of the first request packets to be outputted to the same request output path, and the arbiter selecting and outputting one of the second request packets when one of the second request packets collide with another of the second request packets to be outputted to the same request output path; and a result output circuit for outputting a comparison result indicative signal for causing the input port to transmit packets by a routing pattern of the first and second routing patterns in next cycle, by which more request packets have reached the output port, on the basis of the result of transmission of the first and second request packets.
According to a further aspect of the present invention, a packet switch comprising: a plurality of input ports for accumulating and sequentially transmitting inputted packets; a switching network for outputting the packets inputted from the plurality of input ports, to a target output port sequentially via a plurality of switching elements arranged in the form of lattice, each of the switching elements having a crossbar for selecting and outputting one of the packets when the packets collide with each other to be outputted to the same output path and for returning negative acknowledge signals to an input port, from which one of the packets being not selected has been transmitted; and a switching signal output circuit for counting the number of the negative acknowledge signals returned to the input ports and for outputting a switching indicative signal for causing the input ports to switch a routing pattern when the counted number of the negative acknowledge signals exceeds a predetermined value.
According to a still further aspect of the present invention, a packet switch comprises: a plurality of input ports for accumulating and sequentially transmitting inputted packets and for transmitting request packets by one routing pattern; a switching network for sequentially outputting the packets and the request packets, which have been inputted from the plurality of input ports, to a target output port via a plurality of switching elements arranged in the form of lattice, each of the switching elements including: a crossbar switch for inputting the packets from a plurality of packet input paths and for outputting the packets from one of a plurality of packet output paths in accordance with routing pattern information included in the packets; and an arbiter for inputting the request packets from a plurality of request input paths and for outputting the request packets from one of a plurality of request output paths in accordance with routing pattern information included in the request packets, the arbiter selecting and outputting one of the request packets when one of the request packets collides with another of the request packets to be outputted to the same request output path of the request output paths, and the arbiter returning negative acknowledge signals to a transmission source or sources having transmitted the request packets being not selected; and a switching signal output circuit for counting the number of the negative acknowledge signals returned to the input ports and for outputting a switching indicative signal for causing the input ports to transmit the packets by a routing pattern different from the one routing pattern in next cycle.